{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Техники оптимизации на примерах."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "План: закидывать примеры в quick-bench.com и объяснять что происходит."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### quick-bench.com"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Открыть, показать интерфейс, показать, как пользоваться, рассказать про google benchmark и как он встроен в quick-bench.com, методику измерения:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://quick-bench.com"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://github.com/google/benchmark"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "static void StringCreation(benchmark::State& state) {\n",
    "  // Code inside this loop is measured repeatedly\n",
    "  for (auto _ : state) {\n",
    "    std::string created_string(\"hello\");\n",
    "    // Make sure the variable is not optimized away by compiler\n",
    "    benchmark::DoNotOptimize(created_string);\n",
    "  }\n",
    "}\n",
    "// Register the function as a benchmark\n",
    "BENCHMARK(StringCreation);\n",
    "\n",
    "static void StringCopy(benchmark::State& state) {\n",
    "  // Code before the loop is not measured\n",
    "  std::string x = \"hello\";\n",
    "  for (auto _ : state) {\n",
    "    std::string copy(x);\n",
    "    // Make sure the variable is not optimized away by compiler\n",
    "    benchmark::DoNotOptimize(copy);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(StringCopy);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### std::vector::push_back"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <vector>\n",
    "\n",
    "static const int n = 50000;\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<int> fill_vec()\n",
    "{\n",
    "    std::vector<int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(i);\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<int> fill_vec_with_reserve()\n",
    "{\n",
    "    std::vector<int> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(i);\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMFillVec(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_vec());\n",
    "}\n",
    "BENCHMARK(BMFillVec);\n",
    "\n",
    "static void BMFillVecWithReserve(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_vec_with_reserve());\n",
    "}\n",
    "BENCHMARK(BMFillVecWithReserve);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Два разных способа заполнить std::vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример 1:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <vector>\n",
    "\n",
    "static const int n = 50000;\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<int> fill_vec_with_assign()\n",
    "{\n",
    "    std::vector<int> rv(n, 0);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<int> fill_vec_with_reserve()\n",
    "{\n",
    "    std::vector<int> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(i);\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMFillVecWithAssign(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_vec_with_assign());\n",
    "}\n",
    "BENCHMARK(BMFillVecWithAssign);\n",
    "\n",
    "static void BMFillVecWithReserve(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_vec_with_reserve());\n",
    "}\n",
    "BENCHMARK(BMFillVecWithReserve);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример 2:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "#include <vector>\n",
    "\n",
    "static const int n = 50000;\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<std::string> fill_vec_with_assign()\n",
    "{\n",
    "    std::vector<std::string> rv(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = \"1234567890123456790\";\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<std::string> fill_vec_with_reserve()\n",
    "{\n",
    "    std::vector<std::string> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.emplace_back(\"1234567890123456790\");\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMFillVecWithAssign(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_vec_with_assign());\n",
    "}\n",
    "BENCHMARK(BMFillVecWithAssign);\n",
    "\n",
    "static void BMFillVecWithReserve(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_vec_with_reserve());\n",
    "}\n",
    "BENCHMARK(BMFillVecWithReserve);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### где push_back быстрее?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <deque>\n",
    "#include <list>\n",
    "#include <vector>\n",
    "\n",
    "static const int n = 10000;\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::list<int> fill_list()\n",
    "{\n",
    "    std::list<int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(i);\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<int> fill_vec()\n",
    "{\n",
    "    std::vector<int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(i);\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::deque<int> fill_deq()\n",
    "{\n",
    "    std::deque<int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(i);\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMFillList(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_list());\n",
    "}\n",
    "BENCHMARK(BMFillList);\n",
    "\n",
    "static void BMFillVec(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_vec());\n",
    "}\n",
    "BENCHMARK(BMFillVec);\n",
    "\n",
    "static void BMFillDeque(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_deq());\n",
    "}\n",
    "BENCHMARK(BMFillDeque);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Инициализация отображения int -> int"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <map>\n",
    "#include <unordered_map>\n",
    "\n",
    "static const int n = 50000;\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::map<int, int> fill_map()\n",
    "{\n",
    "    std::map<int, int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::unordered_map<int, int> fill_unordered_map()\n",
    "{\n",
    "    std::unordered_map<int, int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::unordered_map<int, int> fill_unordered_map_reserve()\n",
    "{\n",
    "    std::unordered_map<int, int> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMFillMap(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_map());\n",
    "}\n",
    "BENCHMARK(BMFillMap);\n",
    "\n",
    "static void BMFillUnorderedMap(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_unordered_map());\n",
    "}\n",
    "BENCHMARK(BMFillUnorderedMap);\n",
    "\n",
    "static void BMFillUnorderedMapReserve(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_unordered_map_reserve());\n",
    "}\n",
    "BENCHMARK(BMFillUnorderedMapReserve);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Поиск элемента в отображении"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <map>\n",
    "#include <unordered_map>\n",
    "\n",
    "static const int n = 50000;\n",
    "\n",
    "static std::map<int, int> fill_map()\n",
    "{\n",
    "    std::map<int, int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static std::unordered_map<int, int> fill_unordered_map()\n",
    "{\n",
    "    std::unordered_map<int, int> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMAccessMap(benchmark::State& state) {\n",
    "    const auto x = fill_map();\n",
    "    for (auto _ : state) {\n",
    "        for (int i = n - 1; i >= 0; --i)\n",
    "            benchmark::DoNotOptimize(x.find(i));\n",
    "    }\n",
    "}\n",
    "BENCHMARK(BMAccessMap);\n",
    "\n",
    "static void BMAccessUnorderedMap(benchmark::State& state) {\n",
    "    const auto x = fill_unordered_map();\n",
    "    for (auto _ : state) {\n",
    "        for (int i = n - 1; i >= 0; --i)\n",
    "            benchmark::DoNotOptimize(x.find(i));\n",
    "    }\n",
    "}\n",
    "BENCHMARK(BMAccessUnorderedMap);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Повторить тот же самый пример с `n` = 10 (libstdc++ && libc++, сравнить gcc && clang)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А потом вот этот пример:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <algorithm>\n",
    "#include <cstdlib>\n",
    "#include <map>\n",
    "#include <unordered_map>\n",
    "\n",
    "static const int n = 20;\n",
    "\n",
    "static std::map<int, int> fill_map()\n",
    "{\n",
    "    std::map<int, int> rv;\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static std::unordered_map<int, int> fill_unordered_map()\n",
    "{\n",
    "    std::unordered_map<int, int> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = i;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static std::vector<std::pair<int, int>> fill_vector()\n",
    "{\n",
    "    std::vector<std::pair<int, int>> rv(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv[i] = std::make_pair(i, i);\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static __attribute__((noinline))\n",
    "const int* find_value(const std::vector<std::pair<int, int>>& map_as_vector, const int key)\n",
    "{\n",
    "    for (const auto& pair : map_as_vector)\n",
    "        if (pair.first == key)\n",
    "            return &pair.second;\n",
    "    return nullptr;\n",
    "}\n",
    "\n",
    "static int compare_int_pairs_by_first(const void * a, const void * b)\n",
    "{\n",
    "  const auto* const l = (const std::pair<int, int> *)(a);\n",
    "  const auto* const r = (const std::pair<int, int> *)(b);\n",
    "  return l->first - r->first;\n",
    "}\n",
    "\n",
    "static __attribute__((noinline))\n",
    "const int* bin_find_value(const std::vector<std::pair<int, int>>& map_as_vector, const int key)\n",
    "{\n",
    "    const std::pair<int, int> search_target(key, 0);\n",
    "    auto* pItem = (const std::pair<int, int>*) std::bsearch(\n",
    "        &search_target,\n",
    "        map_as_vector.data(),\n",
    "        map_as_vector.size(),\n",
    "        sizeof(std::pair<int, int>),\n",
    "        compare_int_pairs_by_first);\n",
    "    if (!pItem)\n",
    "        return nullptr;\n",
    "\n",
    "    return &(pItem->second);\n",
    "}\n",
    "\n",
    "static void BMAccessMap(benchmark::State& state) {\n",
    "    const auto x = fill_map();\n",
    "    for (auto _ : state) {\n",
    "        for (int i = n - 1; i >= 0; --i)\n",
    "            benchmark::DoNotOptimize(x.find(i));\n",
    "    }\n",
    "}\n",
    "BENCHMARK(BMAccessMap);\n",
    "\n",
    "static void BMAccessUnorderedMap(benchmark::State& state) {\n",
    "    const auto x = fill_unordered_map();\n",
    "    for (auto _ : state) {\n",
    "        for (int i = n - 1; i >= 0; --i)\n",
    "            benchmark::DoNotOptimize(x.find(i));\n",
    "    }\n",
    "}\n",
    "BENCHMARK(BMAccessUnorderedMap);\n",
    "\n",
    "static void BMAccessVector(benchmark::State& state) {\n",
    "    const auto x = fill_vector();\n",
    "    for (auto _ : state) {\n",
    "        for (int i = n - 1; i >= 0; --i)\n",
    "            benchmark::DoNotOptimize(find_value(x, i));\n",
    "    }\n",
    "}\n",
    "BENCHMARK(BMAccessVector);\n",
    "\n",
    "static void BMAccessVectorBinSearch(benchmark::State& state) {\n",
    "    const auto x = fill_vector();\n",
    "    for (auto _ : state) {\n",
    "        for (int i = n - 1; i >= 0; --i)\n",
    "            benchmark::DoNotOptimize(bin_find_value(x, i));\n",
    "    }\n",
    "}\n",
    "BENCHMARK(BMAccessVectorBinSearch);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Показать его на libstc++ и на libc++, установить `n` значительно выше, показать на libstdc++ и libc++, gcc && clang"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Стоимость умных указателей"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <memory>\n",
    "#include <vector>\n",
    "\n",
    "static const int n = 50000;\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<std::shared_ptr<int>> fill_shared_ptr()\n",
    "{\n",
    "    std::vector<std::shared_ptr<int>> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(std::shared_ptr<int>(new int(i)));\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<std::shared_ptr<int>> fill_make_shared()\n",
    "{\n",
    "    std::vector<std::shared_ptr<int>> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(std::make_shared<int>(i));\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<std::unique_ptr<int>> fill_make_unique()\n",
    "{\n",
    "    std::vector<std::unique_ptr<int>> rv;\n",
    "    rv.reserve(n);\n",
    "    for (int i = 0; i < n; ++i)\n",
    "        rv.push_back(std::make_unique<int>(i));\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMFillSharedPtr(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_shared_ptr());\n",
    "}\n",
    "BENCHMARK(BMFillSharedPtr);\n",
    "\n",
    "static void BMFillMakeShared(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_make_shared());\n",
    "}\n",
    "BENCHMARK(BMFillMakeShared);\n",
    "\n",
    "static void BMFillVecMakeUnique(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(fill_make_unique());\n",
    "}\n",
    "BENCHMARK(BMFillVecMakeUnique);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Работа со строками на примере join"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "#include <vector>\n",
    "\n",
    "static const std::vector<std::string> strings {\n",
    "    \"Yellow Submarine\\n\",\n",
    "    \"\\n\",\n",
    "    \"In the town where I was born\\n\",\n",
    "    \"Lived a man who sailed to sea\\n\",\n",
    "    \"And he told us of his life\\n\",\n",
    "    \"In the land of submarines\\n\",\n",
    "    \"So we sailed up to the sun\\n\",\n",
    "    \"Till we found the sea of green\\n\",\n",
    "    \"And we lived beneath the waves\\n\",\n",
    "    \"In our yellow submarine\\n\"\n",
    "};\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::string join1()\n",
    "{\n",
    "    std::string rv;\n",
    "    for (const auto line: strings)\n",
    "        rv = rv + line;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::string join2()\n",
    "{\n",
    "    std::string rv;\n",
    "    for (const auto& line: strings)\n",
    "        rv = rv + line;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::string join3()\n",
    "{\n",
    "    std::string rv;\n",
    "    for (const auto& line: strings)\n",
    "        rv += line;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::string join4()\n",
    "{\n",
    "    size_t total_size = 0;\n",
    "    for (const auto& line: strings)\n",
    "        total_size += line.size();\n",
    "\n",
    "    std::string rv;\n",
    "    rv.reserve(total_size);\n",
    "    for (const auto& line: strings)\n",
    "        rv += line;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMJoin1(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(join1());\n",
    "}\n",
    "BENCHMARK(BMJoin1);\n",
    "\n",
    "static void BMJoin2(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(join2());\n",
    "}\n",
    "BENCHMARK(BMJoin2);\n",
    "\n",
    "static void BMJoin3(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(join3());\n",
    "}\n",
    "BENCHMARK(BMJoin3);\n",
    "\n",
    "static void BMJoin4(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(join4());\n",
    "}\n",
    "BENCHMARK(BMJoin4);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "сравнить gcc/clang и libstdc++/libc++"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### конвертация числа в строку"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <charconv>\n",
    "#include <sstream>\n",
    "#include <string>\n",
    "\n",
    "const uint64_t x = 12345678900ul;\n",
    "\n",
    "static __attribute__((noinline)) std::string to_string1(uint64_t val)\n",
    "{\n",
    "    std::ostringstream oss;\n",
    "    oss << val;\n",
    "    return oss.str();\n",
    "}\n",
    "\n",
    "static __attribute__((noinline)) std::string to_string2(uint64_t val)\n",
    "{\n",
    "    return std::to_string(val);  // C++11\n",
    "}\n",
    "\n",
    "static __attribute__((noinline)) std::string to_string3(uint64_t val)\n",
    "{\n",
    "    char buf[128];\n",
    "    int n = sprintf(buf, \"%lu\", val);  // C\n",
    "    return {buf, buf + n};\n",
    "}\n",
    "\n",
    "static __attribute__((noinline)) std::string to_string4(uint64_t val)\n",
    "{\n",
    "    char buf[128];\n",
    "    const auto res = std::to_chars(buf, buf + 128, val); // C++17\n",
    "    return {buf, res.ptr};\n",
    "}\n",
    "\n",
    "static void BMToStringStream(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(to_string1(x));\n",
    "}\n",
    "BENCHMARK(BMToStringStream);\n",
    "\n",
    "static void BMToString(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(to_string2(x));\n",
    "}\n",
    "BENCHMARK(BMToString);\n",
    "\n",
    "static void BMToStringSprintf(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(to_string3(x));\n",
    "}\n",
    "BENCHMARK(BMToStringSprintf);\n",
    "\n",
    "static void BMToStringToChars(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(to_string4(x));\n",
    "}\n",
    "BENCHMARK(BMToStringToChars);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Показать clang/gcc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### SSO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "\n",
    "static std::string make_string_14()\n",
    "{\n",
    "    return \"12345678901234\";\n",
    "}\n",
    "\n",
    "static std::string make_string_15()\n",
    "{\n",
    "    return \"123456789012345\";\n",
    "}\n",
    "\n",
    "static std::string make_string_16()\n",
    "{\n",
    "    return \"1234567890123456\";\n",
    "}\n",
    "\n",
    "static std::string make_string_17()\n",
    "{\n",
    "    return \"12345678901234567\";\n",
    "}\n",
    "\n",
    "static std::string make_string_22()\n",
    "{\n",
    "    return \"1234567890123456789012\";\n",
    "}\n",
    "\n",
    "static std::string make_string_23()\n",
    "{\n",
    "    return \"12345678901234567890123\";\n",
    "}\n",
    "\n",
    "static std::string make_string_24()\n",
    "{\n",
    "    return \"123456789012345678901234\";\n",
    "}\n",
    "\n",
    "static void BMMakeString14(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(make_string_14());\n",
    "}\n",
    "BENCHMARK(BMMakeString14);\n",
    "\n",
    "static void BMMakeString15(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(make_string_15());\n",
    "}\n",
    "BENCHMARK(BMMakeString15);\n",
    "\n",
    "static void BMMakeString16(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(make_string_16());\n",
    "}\n",
    "BENCHMARK(BMMakeString16);\n",
    "\n",
    "static void BMMakeString17(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(make_string_17());\n",
    "}\n",
    "BENCHMARK(BMMakeString17);\n",
    "\n",
    "static void BMMakeString22(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(make_string_22());\n",
    "}\n",
    "BENCHMARK(BMMakeString22);\n",
    "\n",
    "static void BMMakeString23(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(make_string_23());\n",
    "}\n",
    "BENCHMARK(BMMakeString23);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Показать clang libc++ / libstdc++"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### allocations caching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "#include <vector>\n",
    "\n",
    "const std::vector<std::vector<double>> data = {\n",
    "    {3.17744692, 5.92620571, 8.25519352, 5.38791914, 0.8765440},\n",
    "    {2.08272032, 8.32814122, 8.80346836, 0.03075542, 7.5883834},\n",
    "    {1.36476568, 4.29295626, 8.35784302, 0.42031432, 1.7609703},\n",
    "    {9.96206844, 1.32851998, 7.53035291, 7.55081274, 2.8070660},\n",
    "    {3.17744692, 5.92620571, 8.25519352, 5.38791914, 0.8765440},\n",
    "    {2.08272032, 8.32814122, 8.80346836, 0.03075542, 7.5883834},\n",
    "    {1.36476568, 4.29295626, 8.35784302, 0.42031432, 1.7609703},\n",
    "    {9.96206844, 1.32851998, 7.53035291, 7.55081274, 2.8070660},\n",
    "    {3.17744692, 5.92620571, 8.25519352, 5.38791914, 0.8765440},\n",
    "    {2.08272032, 8.32814122, 8.80346836, 0.03075542, 7.5883834},\n",
    "    {1.36476568, 4.29295626, 8.35784302, 0.42031432, 1.7609703},\n",
    "    {9.96206844, 1.32851998, 7.53035291, 7.55081274, 2.8070660},\n",
    "};\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<std::string> run()\n",
    "{\n",
    "    std::vector<std::string> rv;\n",
    "    rv.reserve(data.size());\n",
    "    for (const auto& row: data)\n",
    "    {\n",
    "        std::string str;\n",
    "        for (double v : row)\n",
    "            str += std::to_string(v);\n",
    "        rv.push_back(str);\n",
    "    }\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "__attribute__((noinline))\n",
    "static std::vector<std::string> run_alloc_caching()\n",
    "{\n",
    "    std::vector<std::string> rv;\n",
    "    rv.reserve(data.size());\n",
    "    std::string str;\n",
    "    for (const auto& row: data)\n",
    "    {\n",
    "        str.clear();\n",
    "        for (double v : row)\n",
    "            str += std::to_string(v);\n",
    "        rv.push_back(str);\n",
    "    }\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "static void BMRun(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(run());\n",
    "}\n",
    "BENCHMARK(BMRun);\n",
    "\n",
    "static void BMRunAllocCaching(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(run_alloc_caching());\n",
    "}\n",
    "BENCHMARK(BMRunAllocCaching);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### return value and output parameter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "const int N = 1000;\n",
    "int arr[N] = {1, 2, 3, 4, 5};\n",
    "\n",
    "static __attribute__((noinline)) int sum1(int *x, int n)\n",
    "{\n",
    "  int rv = 0;\n",
    "  for (int i = 0; i < n; ++i)\n",
    "    rv += x[i];\n",
    "  return rv;\n",
    "}\n",
    "\n",
    "static __attribute__((noinline)) void sum2(int *x, int n, int *rv)\n",
    "{\n",
    "  *rv = 0;\n",
    "  for (int i = 0; i < n; ++i)\n",
    "    *rv += x[i];\n",
    "}\n",
    "\n",
    "static void BM_sum1(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(sum1(arr, N));\n",
    "}\n",
    "BENCHMARK(BM_sum1);\n",
    "\n",
    "static void BM_sum2(benchmark::State& state) {\n",
    "    int s;\n",
    "    for (auto _ : state) {\n",
    "        sum2(arr, N, &s);\n",
    "        benchmark::DoNotOptimize(s);\n",
    "    }\n",
    "}\n",
    "BENCHMARK(BM_sum2);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Закинуть это дело на godbolt.org и показать, почему так"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Алгоритмы, алгоритмы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <algorithm>\n",
    "#include <vector>\n",
    "\n",
    "static const std::vector<int> v(2000, 1);\n",
    "\n",
    "static __attribute__((noinline))\n",
    "bool contains_algo(const std::vector<int>& v, const int value)\n",
    "{\n",
    "  return std::find(begin(v), end(v), value) != end(v);\n",
    "}\n",
    "\n",
    "static __attribute__((noinline))\n",
    "bool contains_naive(const std::vector<int>& v, const int value)\n",
    "{\n",
    "  for (int i : v)\n",
    "    if (i == value)\n",
    "      return true;\n",
    "  return false;\n",
    "}\n",
    "\n",
    "static void BM_algo(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(contains_algo(v, 2));\n",
    "}\n",
    "BENCHMARK(BM_algo);\n",
    "\n",
    "static void BM_naive(benchmark::State& state) {\n",
    "    for (auto _ : state)\n",
    "        benchmark::DoNotOptimize(contains_naive(v, 2));\n",
    "}\n",
    "BENCHMARK(BM_naive);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сначала показать результат на libc++ LLVM, потом на libstdc++ GNU. Объяснить, почему так:\n",
    "    \n",
    "https://bugs.llvm.org/show_bug.cgi?id=19708"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Специфика однобайтовых типов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <cstdint>\n",
    "#include <vector>\n",
    "\n",
    "const int N = 2000;\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__((noinline)) inc_v1(std::vector<T>& v) {\n",
    "  for (int i = 0; i < v.size(); ++i)\n",
    "    ++v[i];\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__((noinline)) inc_v2(std::vector<T>& v) {\n",
    "  for (int i = 0, count = v.size(); i < count; ++i)\n",
    "    ++v[i];\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__((noinline)) inc_v3(std::vector<T>& v) {\n",
    "  for (auto i = v.begin(), e = v.end(); i != e; ++i)\n",
    "    ++(*i);\n",
    "}\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__((noinline)) inc_v4(std::vector<T>& v) {\n",
    "  for (auto& i : v)\n",
    "    ++i;\n",
    "}\n",
    "\n",
    "static void BM_inc8_v1(benchmark::State& state) {\n",
    "  std::vector<std::uint8_t> v(N* 4);\n",
    "  for (auto _ : state) {\n",
    "    inc_v1(v);\n",
    "    benchmark::DoNotOptimize(v);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(BM_inc8_v1);\n",
    "\n",
    "static void BM_inc8_v2(benchmark::State& state) {\n",
    "  std::vector<std::uint8_t> v(N * 4);\n",
    "  for (auto _ : state) {\n",
    "    inc_v2(v);\n",
    "    benchmark::DoNotOptimize(v);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(BM_inc8_v2);\n",
    "\n",
    "static void BM_inc8_v3(benchmark::State& state) {\n",
    "  std::vector<std::uint8_t> v(N * 4);\n",
    "  for (auto _ : state) {\n",
    "    inc_v3(v);\n",
    "    benchmark::DoNotOptimize(v);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(BM_inc8_v3);\n",
    "\n",
    "static void BM_inc8_v4(benchmark::State& state) {\n",
    "  std::vector<std::uint8_t> v(N * 4);\n",
    "  for (auto _ : state) {\n",
    "    inc_v4(v);\n",
    "    benchmark::DoNotOptimize(v);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(BM_inc8_v4);\n",
    "\n",
    "static void BM_inc32_v1(benchmark::State& state) {\n",
    "  std::vector<std::uint32_t> v(N);\n",
    "  for (auto _ : state) {\n",
    "    inc_v1(v);\n",
    "    benchmark::DoNotOptimize(v);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(BM_inc32_v1);\n",
    "\n",
    "static void BM_inc32_v3(benchmark::State& state) {\n",
    "  std::vector<std::uint32_t> v(N);\n",
    "  for (auto _ : state) {\n",
    "    inc_v3(v);\n",
    "    benchmark::DoNotOptimize(v);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(BM_inc32_v3);\n",
    "\n",
    "static void BM_inc32_v4(benchmark::State& state) {\n",
    "  std::vector<std::uint32_t> v(N);\n",
    "  for (auto _ : state) {\n",
    "    inc_v4(v);\n",
    "    benchmark::DoNotOptimize(v);\n",
    "  }\n",
    "}\n",
    "BENCHMARK(BM_inc32_v4);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### branch predictor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <algorithm>\n",
    "\n",
    "__attribute__((noinline))\n",
    "static int run(const std::vector<int>& v)\n",
    "{\n",
    "  // code inside loop must be complex enough\n",
    "  // for vectorization, otherwise vectorized\n",
    "  // loop won't show branch predictor effect\n",
    "  //\n",
    "  // inter-iteration dependency should be ok\n",
    "  // for modern (2019) compilers\n",
    "  int rv = 0;\n",
    "  for (int x : v)\n",
    "    if (x < 5)\n",
    "      rv = x + rv / 2;\n",
    "  return rv;\n",
    "}\n",
    "\n",
    "constexpr int num_elements = 500;\n",
    "\n",
    "static std::vector<int> get_rand_vector()\n",
    "{\n",
    "  std::vector<int> rv;\n",
    "  rv.resize(num_elements);\n",
    "  for (int i = 0; i < num_elements; ++i)\n",
    "    rv[i] = rand() % 10;\n",
    "  return rv;\n",
    "}\n",
    "\n",
    "static std::vector<int> get_sorted_vector()\n",
    "{\n",
    "  auto rv = get_rand_vector();\n",
    "  std::sort(rv.begin(), rv.end());\n",
    "  return rv;\n",
    "}\n",
    "\n",
    "static void Sorted(benchmark::State& state) {\n",
    "  for (auto _ : state) {\n",
    "    state.PauseTiming();\n",
    "    const auto v = get_sorted_vector();\n",
    "    state.ResumeTiming();\n",
    "\n",
    "    benchmark::DoNotOptimize(run(v));\n",
    "  }\n",
    "}\n",
    "BENCHMARK(Sorted);\n",
    "\n",
    "static void Unsorted(benchmark::State& state) {\n",
    "  volatile int sum = 0;\n",
    "  for (auto _ : state) {\n",
    "    state.PauseTiming();\n",
    "    const auto v = get_rand_vector();\n",
    "    state.ResumeTiming();\n",
    "      \n",
    "    benchmark::DoNotOptimize(run(v));\n",
    "  }\n",
    "}\n",
    "BENCHMARK(Unsorted);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Выступление Matt godbolt на cppcon2019](https://www.youtube.com/watch?v=HG6c4Kwbv4I) о том как исправление одного if в сторону БОЛЬШЕГО числа вычислений в программе ускорило программу на 36%. Потому что branch predictor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Доклад про simdjson (самый быстрый парсер json в 2019)](https://www.youtube.com/watch?v=wlvKAT7SZIQ) и низкоувроневые оптимизации (в т.ч. branch predictor)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример с branch predictor, который был актуален много лет назад, но потерял свой эффект из-за векторизации цикла компилятором:\n",
    "https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В стандрте С++20 вводятся `[[likely]]`, `[[unlikely]]` - подсказки от программиста компилятору:\n",
    "https://en.cppreference.com/w/cpp/language/attributes/likely\n",
    "\n",
    "Компилятор сможет учитывать вероятность сценария при оптимизации. Возможно, компилятор сможет построить jump-ы таким образом, чтобы branch-predictor-у было проще угадывать правильный переход (но это не точно)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Домашнее задание по оптимизациям"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Выдать задание:\n",
    "\n",
    "* рассказать про задачу поиска по телефону\n",
    "* как ставится балл за задачу\n",
    "* какие оптимизации запрещено применять"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Правила оптимизации"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Убедитесь, что оптимизировать действительно надо.\n",
    "2. Напишите performance-тест для измерения производительности\n",
    "3. Одна гипотеза - одно измерение\n",
    "4. Отпрофилировать и найти самое тяжёлое место\n",
    "5. Оптимизация сверху вниз (ни в коем случае не спускаться на ступеньку ниже, пока не поймём, что возможности ступеньки выше исчерпаны)\n",
    "  * Нужны ли эти вычисления? (нет - убираем / кешируем - работает примитивная логика)\n",
    "  * Дело в асимптотике алгоритма? (да - меняем алгоритм - работает теория алгоритмов)\n",
    "  * Можно ли ускорить на уровне абстракций С++? (примитивные примеры: `reserve`, `make_shared`, `std::string::append`, `mutex -> atomic` etc - работает знание основ языка)\n",
    "  * Можно ли ускорить на уровне абстракций ОС? (примитивные примеры: virtual memory organization и разбиение на процессы - работает знание ОС - не в рамках этого курса)\n",
    "  * Welcome to michroarchitecture optimization guide! (примитивные примеры: strict aliasing, loops unrolling, vectorization etc. - вопрос, скорее всего, не будет покрываться в рамках курса)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
